package 数据结构.LinkList.diamond;

/*LeetCode25 K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

        k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

        你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换*/
public class kExchange {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
        public static void printList(ListNode head) {
            ListNode node = head;
            while (node != null) {
                System.out.print(node.val + "-->");
                node = node.next;
            }
        }
        public static void main(String[] args) {
            ListNode head = new ListNode(1);
            ListNode two = new ListNode(2);
            ListNode three = new ListNode(3);
            ListNode four = new ListNode(4);
            ListNode five = new ListNode(5);
            head.next = two;
            two.next = three;
            three.next = four;
            four.next=five;
            ListNode hea = reverseKGroup(head, 2);
        }
//循环之后各个节点的位置应该在哪：参照这一次循环各个节点的关系，下一个循环的各节点关系应该仍然是一样的
/*// 【如第一次循环start和pre的关系是：pre在start的前面 那么下一次循环也应该是pre在start的前面】
        *//*pre.next = reverse(start); 这个的真正含义：
        * 1.解读
        *当 pre.next = reverse(start); 设置 pre 的 next 时，它设置的是当前 pre 所指向的节点的 next。
                也就是说 在当pre.next=reverse(start)时
                如pre的val 是1 那么其实这里设置的是让 1 的next指向 reverse(start)，跟pre其实无关
          ege：当后面执行 pre = start; 时，pre 这个指针本身指向了新的节点（即 start），
                但这不会改变之前设置的 pre.next 的值，因为那时的 pre 指向的节点已经通过
                pre.next = reverse(start); 操作完成了连接。
                * 【即之前在pre.next设置时，是将此时的pre所指向的地址【1】去设置他的next指针
                 而后面在设置pre=start时，这里的pre的地址已经不是【1】了，所以之前的也不会改
          2，所以其实都能说的通了，当操作head2时，head也会发生改变，原因其实就是因为head2操作时，操作的时【如head是1】1的节点
          * 然后head也是指1 这个节点，所以他们都会改变
          3.变量名只是工具。【具体的是当赋值后对那个指向的地址进行一个改变】
          5.在写的时候，因为变量名只是工具，所以在各种变化之后呢，应该对值进行修改，而不是变量
          即：3.  todo:每当val/next变了之后，都可以看作是一个新节点，即写出他的val和next，不要用前面的变量代替
             这样子就不会混淆了 即： cur.next = pre 那么 就重新写cur  val：1  next ：null【不写pre】
             *                                      不是    cur  val: 1  next:  pre [X] 写变量并没有意义，关键是背后指向的地址
                                  pre=cur                  pre   val：1 next：null
                                  cur=next                 cur   val：2  next：3【都是值表示】

          6.这是移动的目的所在：
            循环之后各个节点的位置应该在哪：参照这一次循环各个节点的关系，下一个循环的各节点关系应该仍然是一样的
          即【如第一次循环start和pre的关系是：pre在start的前面 那么下一次循环也应该是pre在start的前面】
          7.赋值时  pre=cur   是将变量pre变成cur  而不是将pre原先所指向的节点 1 变成cur！！！
          8.在做题时：虽然写着：pre =1 pre.next=xx，但其实内心要想着  pre背后是什么，在纸上画出
          9.之前的想法全是错的，想反了，我们是要让 比如
          * null--1--2--3--4
          * 如果现在要 null--2--1 是先想要让null指向2 然后再看此时的有哪个变量指向的是null 再去利用这个变量做事情
          *  即 pre.next = reverse(start)
          * 而不是先想着让per.next 指向什么
        * */
        private static ListNode reverseKGroup(ListNode head, int k) {
            //利用递归的思想
            //1.mind：分块+反转链表
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode pre = dummy;
            ListNode end = dummy;

            while (end.next != null) {
                /*for (int i = 0; i < k; i++) {
                    end = end.next;
                }
                ListNode start = pre.next;
                //所以这里得先去记录
                ListNode next = end.next;
                //这里去将end.next置空：方便
                end.next = null;
                //得到范围之后[范围：start-end【因为end.next置空了】】：去反转他们
                pre.next = reverse(start);
                start.next = next;
                pre = start;
                end = pre;
                //*/
                for (int i = 0; i < k && end != null; i++) end = end.next;
                if (end == null) break;
                ListNode start = pre.next;
                ListNode next = end.next;
                end.next = null;
                pre.next = reverse(start);
                start.next = next;
                //那么他之前的next的作用呢？
             /* 是后面设置了pre=start 那前面的pre.next的作用会不会被抵消掉，还是说pre.next设置的是此时pre的地址的next，
                当后面pre=start的时候，地址不是原来的地址了，不会对前面的pre.next的设置进行覆盖
                你的理解是正确的。
                当 pre.next = reverse(start); 设置 pre 的 next 时，它设置的是当前 pre 所指向的节点的 next。
                也就是说 在当pre.next=reverse(start)时
                如pre的val 是1 那么其实这里设置的是让 1 的next指向 reverse(start)，跟pre其实无关
                当后面执行 pre = start; 时，pre 这个指针本身指向了新的节点（即 start），
                但这不会改变之前设置的 pre.next 的值，因为那时的 pre 指向的节点已经通过
                pre.next = reverse(start); 操作完成了连接。【即之前在pre.next设置时，是将此时的pre所指向的地址【1】去设置他的next指针
                                                          而后面在设置pre=start时，这里的pre的地址已经不是【1】了，所以之前的也不会改*/
                pre = start;
                end = pre;
            }
            printList(dummy.next);
            System.out.println(dummy.next.next.val);
            return dummy.next;
        }

        //反转链表
        //利用前后两个节点
        //要点：1.先弄一个pre=null，因为是反转，所以原先的head节点的下一个节点是null
        //     2.让他们逐一反着指向即可。
        //      记录节点的前提：后面的指向变了但仍要原来的
        //      3.认知错误：所以以后都用数代替 不用变量表示【这样子也不会导致错误，可避免混淆】
   /*          pre = cur;//todo：理解：这里是节点的移动 即将pre指向cur所指向的节点位置
            1. 先前的cur是：val：1  next：   ·指向pre的位置，因为是null，所以是null，这里别写成pre
        pre=cur==> pre：val     next：null
           2.  将 next 认为是 pre 容易产生认知错误。为了避免混淆，应该明确 cur.next = pre 这个操作的实际效果。
              具体来说，cur.next 是一个指针，指向一个节点，这个节点可能是 pre 当前指向的节点，但 cur.next 本身并不是 pre。
           3.  todo:每当val/next变了之后，都可以看作是一个新节点，即写出他的val和next，不要用前面的变量代替
             这样子就不会混淆了 即： cur.next = pre 那么 就重新写cur  val：1 next ：null【不写pre】
                                  pre=cur                  pre   val：1 next：null
                                  cur=next                 cur   val：2  next：3*/
        //利用cur和cur.next的判断条件：cur!=null：需要处理链表中的每个节点。
        //                         cur.next!=null 需要处理链表中的大部分节点，但不包括最后一个节点。
        public static ListNode reverse(ListNode head) {
            ListNode pre = null;
            ListNode cur = head;
            //这里利用
            while (cur != null) {
                //记录了cur.next; 反转链表；
                //结合①②所以这里得去先记录next节点
                //如果是 pre null  c链表 1--2--3--4
                ListNode next = cur.next;//next:2
                //①当遇到这里：即cur.next的指向变了
                cur.next = pre; //将cur的next设置为null
                //这里是指针的移动
                pre = cur;//todo：理解：这里是节点的移动 即将pre指向cur所指向的节点位置
                          //先前的cur是：val：1  next：指向pre的位置，因为是null，所以是null，这里别写成pre
                          //  pre=cur：  pre：val  next：null
                //将 next 认为是 pre 容易产生认知错误。为了避免混淆，应该明确 cur.next = pre 这个操作的实际效果。
                // 具体来说，cur.next 是一个指针，指向一个节点，这个节点可能是 pre 当前指向的节点，
                // 但 cur.next 本身并不是 pre。
                //todo:每当val/next变了之后，都可以看作是一个新节点，即写出他的val和next，不要用前面的变量代替
                //这样子就不会混淆了 即： cur.next = pre 那么 就重新写cur  val：1 next ：null【不写pre】
                //                     pre=cur                  pre   val：1 next：null
                //                     cur=next                 cur   val：2  next：3
                //②然后这里又想要cur=cur.next【但这里是想要原先的next的】
                //这里让cur=next，就是比如 1--2--3--4
                //此时的pre节点是3 那么cur是4
                //如果pre是4 那么cur是null【此时循环结束，所以pre是头节点，即最后一个，即使cur更靠后，但他是null】
                cur = next;
            }
/*            printList(cur);
            System.out.println();*/
            //为什么pre是头节点而不是cur：因为上面的循环判断条件和最后一行代码
            return pre;
        }
        //详解；
        private static ListNode reverseKGroup2(ListNode head, int k) {
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode pre=dummy;
        ListNode start=dummy;
        ListNode end=dummy;
        while (end.next!=null){
            for (int i = 0; i < k; i++) {
                end=end.next;
            }
            ListNode tem=end.next;
            start=pre.next;
            end.next=null;
            pre.next=reverse2(start);
            start.next=tem;
            pre=start;
            end=pre;
        }
        printList(dummy.next);
        return null;
        }

        private static ListNode reverse2(ListNode head) {
            //让里面的形成反转链表
            ListNode pre=null;
            ListNode cur=head;
            while (cur!=null){
                ListNode next=cur.next;//3
                cur.next=pre;//1
                pre=cur;
                cur=next;//2
            }
            return pre;
        }

        }
    }
